МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
кафедра ЗІ
Звіт
до лабораторної роботи № 1
з курсу: "Програмний захист інформації "
на тему: “ Дослідження алгоритмів архівації ”
Мета роботи: Розглянути основні методи стиску інформації. Навчитися на практиці реалізовувати дані алгоритми.
Засвоїти поняття:
• архівація даних; • архів даних;
• програма-архіватор; • неперервне архівування;
• багатотомні архіви; • архіви, які містять засіб для розшаровування (SFX);
• відновлення даних; • відновлювальні томи;
• коментар до архіву; • протокол помилок.
Вміти:
• створювати архіви даних;
• переглядати вміст архіву, видобувати файли, від ображати коментарі та інформацію про архів;
• відновлювати фізично пошкоджений архів;
• видобувати файли за допомогою середовища WinRAR
Завдання:
Розробити програму стиснення файлів одним із наведених у таблиці №1 алгоритмом згідно свого варіанту.
Варіант
Алгоритми програм
5
Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)
Короткі теоретичні відомості:
Всі алгоритми стиснення оперують вхідним потоком даних, мінімальною одиницею яких є біт, а максимальною – декілька біт, байт або декілька байтів.
Метою процесу стиснення є отримання більш компактного вихідного потоку інформаційних одиниць з некомпактного вхідного потоку за допомогою перетворення.
Основними технічними характеристиками процесів стиснення і результатів їх роботи є :
• степінь стиснення (compress rating) або відношення (retion) об’ємів вхідного і вихідного потоків;
• швидкість стиснення – час, який витрачається на стиснення деякого об’єму інформації вхідного потоку, до отримання з нього еквівалентного вихідного потоку;
• якість стиснення – величина, яка вказує, на скільки сильно упакований вихідний потік, за допомогою застосування до нього повторного стиснення за цим або іншим алгоритмом.
Всі способи стиснення можна поділити на дві категорії: зворотнє і не зворотнє.
Під зворотнім стисненням розуміють таке перетворення вхідного потоку даних, при якому вихідний потік, в контексті певного формату даних, представляє достатньо схожий за зовнішніми характеристиками на вхідний потік об’єкт, але відрізняється від нього об’ємом. Рівень схожості вхідного і вихідного потоків визначається рівнем відповідності деяких властивостей об’єкта (тобто, стисненої і не стисненої інформації у відповідності до деякого визначеного формату даних).
Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)
Даний алгоритм відрізняють висока швидкість роботи як при упаковці, так і при розпаковуванні, досить скромні вимоги до пам'яті і проста апаратна реалізація.
Недолік - низька міра стиснення в порівнянні з схемою двоступінчастого кодування.
Передбачимо, що у нас є словник, що зберігає рядки тексту і що містить порядку від 2-ох до 8-ми тисяч пронумерованих гнізд. Запишемо в перших 256 гнізд рядки, що складаються з одного символу, номер якого дорівнює номеру гнізда.
Алгоритм переглядає вхідний потік, розбиваючи його на підрядки і додаючи нові гнізда в кінець словника. Прочитаємо декілька символів в рядок s і знайдемо в словнику рядок t - щонайдовший префікс s.
Хай він знайдений в гнізді з номером n. Виведемо число n у вихідний потік, перемістимо покажчик вхідного потоку на length(t) символів вперед і додамо в словник нове гніздо, що містить рядок t+c, де с - черговий символ на вході (відразу після t). Алгоритм перетворить потік символів на вході в потік індексів комірок словника на виході.
При практичній реалізації цього алгоритму слід врахувати, що будь-яке гніздо словника, окрім найперших, таких, що містять одно-символьні ланцюжки, зберігає копію деякого іншого гнізда, до якої в кінець приписаний один символ. Внаслідок цього можна обійтися простою обліковою структурою з одним зв'язком.
Приклад:
ABCABCABCABCABCABC - 1 2 3 4 6 5 7 7 7
1
A
2
B
3
C
4
AB
5
BC
6
CA
7
ABC
8
CAB
9
BCA...
